class Solution(object):
    def distributeCoins(self, root):
        d_diff = {}

        def search(node):
            left = 0
            right = 0
            if node.left:
                left = search(node.left)
            if node.right:
                right = search(node.right)
            d_diff[node] = node.val + left + right - 1
            return d_diff[node]

        self.c = 0

        def judge(node):
            self.c += abs(d_diff[node])
            if node.left:
                judge(node.left)
            if node.right:
                judge(node.right)

        search(root)
        judge(root)
        return self.c
